"""
难度：中等
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
"""
"""
回溯算法在二维矩阵 board 中按照上下左右四个方向递归搜索。设函数 backtrack(i, j, index) 表示从 board[i][j] 出发，能否搜索到单词字母 word[index]，以及 index 位置之后的后缀子串。如果能搜索到，则返回 True，否则返回 False。backtrack(i, j, index) 执行步骤如下：
如果 ，而且 index 已经到达 word 字符串末尾，则返回 True。
如果 ，而且 index 未到达 word 字符串末尾，则遍历当前位置的所有相邻位置。如果从某个相邻位置能搜索到后缀子串，则返回 True，否则返回 False。
如果 ，则当前字符不匹配，返回 False
"""

from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directs = [(0,1),(0,-1),(1,0),(-1,0)]
        rows = len(board)
        if rows == 0:
            return False
        cols = len(board[0])
        visited = [[ False for _ in range(cols)] for _ in range(rows)]

        def backtrack(i,j,index):
            if index == len(word)-1:
                return board[i][j] == word[index]
            if board[i][j] == word[index]:
                visited[i][j] = True
                for direct in directs:
                    new_i = i + direct[0]
                    new_j = j + direct[1]
                    if 0 <= new_i<rows and 0 <= new_j<cols and visited[new_i][new_j] ==False:
                        if backtrack(new_i,new_j,index+1):
                            return True
                visited[i][j] = False
        
        for  i in range(rows):
            for j in range(cols):
                if backtrack(i,j,0):
                    return True
        return False
if __name__ =="__main__":
    board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
    word = "ABCCED"
    solu = Solution()
    print(solu.exist(board,word))